package com.dhu.graph.weightGraph;

import com.dhu.graph.basic.edge.Edge;
import com.dhu.graph.basic.GraphImpls.EdgeWeightGraph;
import com.dhu.graph.utils.ArrayQueue;
import com.dhu.graph.utils.MinPQ;

/**
 * @Author ：snow
 * @Date   ：Created in 2020-05-08
 * @Description：
 * 延时性Prim算法，连通无向图生成最小生成树，将最小生成树的所有边存储在队列mst中
 * 延时性是针对于失效边而言的，延时性就是不在一旦横切边失效就删除，而是在统一删除的时候删除
 * 而很切边是指的是连接已经归入到最小生成树中的顶点和还未归入最小生成树的顶点，
 * 横切边的失效： 在一个顶点归入最小生成树后，要在该顶点的所有的横切边中选择权重最小的边加入最小生成树，
 * 然后就要访问并标记这个顶点加入最小生成树的边的令一端的顶点，当遇到两端都已经被标记的边时，证明这是一个失效的边
 *
 * @ Modified By：
 * @ Version:
 */
public class LazyPrimMST {
    private boolean[] marked;
    private ArrayQueue<Edge> mst;
    private MinPQ<Edge> pq;

    /**
     * 在构造器中就即使的生成最小生成树，这是一种设计模式
     * @param G
     */
    public LazyPrimMST(EdgeWeightGraph G){
        this.marked = new boolean[G.V()];
        mst = new ArrayQueue<>();
        pq = new MinPQ<>();
        visit(G, 0);
        while (! pq.isEmpty()){
            Edge e = pq.deleteMin();
            int v = e.either(), w = e.other(v);
            if (marked[v] && marked[w]) continue;   // 失效边
            mst.enqueue(e);
            if (!marked[v]) visit(G, v);
            else visit(G, w);
        }

    }


    /**
     * 访问一个顶点，并将与这个顶点连接的所有未标记的顶点的边加入pq
     * @param G
     * @param v
     */
    private void visit(EdgeWeightGraph G, int v){
        marked[v] = true;
        for (Edge edge : G.adj(v)) {
            if (!marked[edge.other(v)]) pq.insert(edge);
        }

    }
    public Iterable<Edge> edges(){
        return this.mst;
    }
}
